package com.lwl.leetcode;

import org.junit.Test;

/**
 * @author lwl
 * @Description TODO
 * @date 2023/8/1 11:19
 */
public class Code44IsMatch {

    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int n = s.length();
        int m = p.length();
        int a = 100;
        System.out.println(a);
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[n][m] = true;
        for (int pIndex = m - 1; pIndex >= 0; pIndex--) {
            dp[n][pIndex] = p.charAt(pIndex) == '*' && dp[n][pIndex + 1];
        }

        for (int pIndex = m - 1; pIndex >= 0; pIndex--) {
            for (int sIndex = n - 1; sIndex >= 0; sIndex--) {
                if (s.charAt(sIndex) == p.charAt(pIndex) || p.charAt(pIndex) == '?') {
                    dp[sIndex][pIndex] = dp[sIndex + 1][pIndex + 1];
                }
                if (p.charAt(pIndex) == '*') {
//                    for (int i = sIndex; i <= n; i++) {
//                        if (dp[i][pIndex + 1]) {
//                            dp[sIndex][pIndex] = true;
//                            break;
//                        }
//                    }
                }
            }
        }

        return dp[0][0];
    }

    public boolean isMatch2(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int n = s.length();
        int m = p.length();
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[n][m] = true;
        for (int pIndex = m - 1; pIndex >= 0; pIndex--) {
//            return p.charAt(pIndex) == '*' && process1(s, sIndex, p, pIndex + 1, dp);
            dp[n][pIndex] = p.charAt(pIndex) == '*' && dp[n][pIndex + 1];
        }

        for (int pIndex = m - 1; pIndex >= 0; pIndex--) {
            for (int sIndex = n - 1; sIndex >= 0; sIndex--) {
                if (s.charAt(sIndex) == p.charAt(pIndex) || p.charAt(pIndex) == '?') {
//                    return process(s, sIndex + 1, p, pIndex + 1);
                    dp[sIndex][pIndex] = dp[sIndex + 1][pIndex + 1];
                }
                if (p.charAt(pIndex) == '*') {
//                    // 匹配一个，下一个匹配不匹配有下一层递归负责
//                    if (process(s, sIndex + 1, p, pIndex)) {
//                        return true;
//                    }
//                    // 一个都不匹配
//                    return process(s, sIndex, p, pIndex + 1);
                    for (int i = sIndex; i <= n; i++) {
                        if (dp[i][pIndex + 1]) {
                            dp[sIndex][pIndex] = true;
                            break;
                        }
                    }
                }
//                return false;
            }
        }

        return dp[0][0];
    }

    public boolean isMatch1(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int[][] dp = new int[s.length() + 1][p.length() + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
//        return process(s, 0, p, 0);
        return process1(s, 0, p, 0, dp);
    }

    private boolean process1(String s, int sIndex, String p, int pIndex, int[][] dp) {
        if (dp[sIndex][pIndex] != -1) {
            return dp[sIndex][pIndex] == 1;
        }
        if (sIndex == s.length()) {
            if (pIndex == p.length()) {
                return true;
            }
//            return isLegal(p, pIndex);
            return p.charAt(pIndex) == '*' && process1(s, sIndex, p, pIndex + 1, dp);
        }
        if (pIndex == p.length()) {
            return false;
        }

        if (s.charAt(sIndex) == p.charAt(pIndex) || p.charAt(pIndex) == '?') {
            dp[sIndex][pIndex] = process1(s, sIndex + 1, p, pIndex + 1, dp) ? 1 : 0;
            return dp[sIndex][pIndex] == 1;
        }
        if (p.charAt(pIndex) == '*') {
            // 匹配一个，下一个匹配不匹配有下一层递归负责
            dp[sIndex][pIndex] = process1(s, sIndex + 1, p, pIndex, dp) ? 1 : 0;
            if (dp[sIndex][pIndex] == 1) {
                return true;
            }
            // 一个都不匹配
            dp[sIndex][pIndex] = process1(s, sIndex, p, pIndex + 1, dp) ? 1 : 0;
            return dp[sIndex][pIndex] == 1;
        }
        dp[sIndex][pIndex] = 0;
        return false;
    }

//    private boolean process(String s, int sIndex, String p, int pIndex) {
//        if (sIndex == s.length()) {
//            if (pIndex == p.length()) {
//                return true;
//            }
//            return isLegal(p, pIndex);
//        }
//        if (pIndex == p.length()) {
//            return false;
//        }
//
//        if (s.charAt(sIndex) == p.charAt(pIndex) || p.charAt(pIndex) == '?') {
//            return process(s, sIndex + 1, p, pIndex + 1);
//        }
//        if (p.charAt(pIndex) == '*') {
//            // 匹配一个，下一个匹配不匹配有下一层递归负责
//            if (process(s, sIndex + 1, p, pIndex)) {
//                return true;
//            }
//            // 一个都不匹配
//            return process(s, sIndex, p, pIndex + 1);
//        }
//        return false;
//    }

    private boolean isLegal(String p, int pIndex) {
        for (int i = pIndex; i < p.length(); i++) {
            if (p.charAt(i) != '*') {
                return false;
            }
        }
        return true;
    }

    @Test
    public void test() {
        /*
        false
        true
        false
        true
        true
         */
        System.out.println(isMatch("aa", "a"));
        System.out.println(isMatch("aa", "*"));
        System.out.println(isMatch("", "****"));
        System.out.println(isMatch("cb", "?a"));
        System.out.println(isMatch("cb", "?b"));
        System.out.println(isMatch("cb", "*?b"));
    }

}
